
#ifndef NDK_DAY44_BST_H
#define NDK_DAY44_BST_H

#include <iostream>
#include <queue>
#include <android/log.h>

using namespace std;

// c++   Map  MlitiMap  红黑树
// java Map 和 c++ Map 比较
template<class K, class V>
struct TreeNode {
public:
    TreeNode<K, V> *left = NULL;
    TreeNode<K, V> *right = NULL;
    K key;
    V value;
    int height;// 当前树的高度

    TreeNode(K key, V value) : height(1) {// 初始节点的高度为 1
        this->right = NULL;
        this->left = NULL;
        this->key = key;
        this->value = value;
    }

    TreeNode(TreeNode<K, V> *pNode) : height(pNode->height) {
        this->left = pNode->left;
        this->right = pNode->right;
        this->key = pNode->key;
        this->value = pNode->value;
    }
};

template<class K, class V>
class AVL {
    TreeNode<K, V> *root;// 根节点
    int count;// 总节点的个数

public:
    AVL() {
        root = NULL;
        count = 0;
    }

    ~AVL() {
        // 大家自己去完成
    }

public:

// 新增 （修改）
    void put(K key, V value) {
        root = addNode(root, key, value);
    }

    // 查找 （自己实现）
    V *get(K key) {
        return NULL;
    }
    int size() {
        return count;
    }

    // 写完
    bool contains(K key) {
        TreeNode<K, V> *node = root;

        while (node) {
            if (node->key == key) {
                return node->value;
            } else if (node->key > key) {
                node = node->left;
            } else {
                node = node->right;
            }
        }
        return false;
    }

// 删除 (最主要的内容)
    void remove(K key) {
        // 分情况解决
        root = removeNode(root, key);
    }

    // 中序遍历：所有元素已经排序好了
    void inOrderTraverse(void (*fun)(K, V)) {
        inOrderTraverse(root, fun); // 传入根节点和 打印方法fun。
    }

    // 层序遍历
    void levelTraverse(void (*fun)(K, V)) {
        if (root == NULL) {
            return;
        }
        TreeNode<K, V> *node = root;
        queue<TreeNode<K, V> *> nodes;
        nodes.push(node);
        while (!nodes.empty()) {
            node = nodes.front();
            fun(node->key, node->value);
            nodes.pop();

            if (node->left) {
                nodes.push(node->left);
            }
            if (node->right) {
                nodes.push(node->right);
            }
        }
    }

private:
    int getHeight(TreeNode<K, V> *pNode) {
        return pNode ? pNode->height : 0;
    }

    // 四个旋转操作
    // 右旋
    TreeNode<K, V> *R_Rotation(TreeNode<K, V> *pNode) {
        TreeNode<K, V> *left = pNode->left; // 1.原来的左孩子作为根节点。用作返回
        pNode->left = left->right;  // 2.左节点的右孩子，将来作为原根节点的左孩子。
        left->right = pNode;        // 3.原来的根节点，作为新根节点的右孩子。

        //  更新高度
        pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
        left->height = max(getHeight(left->left), getHeight(left->right)) + 1;
        return left;
    }

    // 左旋
    TreeNode<K, V> *L_Rotation(TreeNode<K, V> *pNode) {
        TreeNode<K, V> *right = pNode->right; // 1.原节点的左节点作为根节点。用作返回
        pNode->right = right->left;     // 2.右节点的左孩子，将要作为原根节点的右孩子。
        right->left = pNode;            // 3.原节点，作为新节点的左孩子。

        //  更新高度
        pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
        right->height = max(getHeight(right->left), getHeight(right->right)) + 1;
        return right;
    }

    // 先左旋再右旋
    TreeNode<K, V> *L_R_Rotation(TreeNode<K, V> *pNode) {
        pNode->left = L_Rotation(pNode->left); // 先对其左孩子，以它为根节点左旋操作。返回值作为左节点。
        return R_Rotation(pNode);              // 以当前节点，进行右旋操作。
    }
    // 先右旋再左旋
    TreeNode<K, V> *R_L_Rotation(TreeNode<K, V> *pNode) {
        pNode->right = R_Rotation(pNode->right); // 先对其左孩子，进行右旋操作。返回值作为右节点。
        return L_Rotation(pNode);                // 以当前节点，进行左旋
    }

    // 返回一个节点 (逻辑问题？ 1 ，2) ，多去理解
    TreeNode<K, V> *addNode(TreeNode<K, V> *pNode, K key, V value) {
        if (pNode == NULL) {
            count++;
            return new TreeNode<K, V>(key, value);
        }

        if (pNode->key > key) { // 小，插入到左边
            pNode->left = addNode(pNode->left, key, value);
            if (getHeight(pNode->left) - getHeight(pNode->right) == 2) {
                // 调整 , 不能简简单单的就做一次右旋
                if (getHeight(pNode->left->right) > getHeight(pNode->left->left)) {
                    // 当左孩子的右孩子的高度 大于 左孩子的左孩子的高度。要先左旋再右旋。
                    pNode = L_R_Rotation(pNode);  // 先左旋，再右旋
                } else {
                    // 当左孩子的右孩子的高度 小于= 左孩子的左孩子的高度。只需要一次右旋操作。
                    pNode = R_Rotation(pNode);
                }
            }
        } else if (pNode->key < key) { // 大，插入到右边子树
            pNode->right = addNode(pNode->right, key, value);
            if (getHeight(pNode->right) - getHeight(pNode->left) == 2) {
                // 调整
                if (getHeight(pNode->right->left) > getHeight(pNode->right->right)) {
                    // 当右孩子的左孩子高度 大于 右孩子的右孩子高度。要先右旋再左旋。
                    pNode = R_L_Rotation(pNode); // 先右旋，再左旋。
                } else {
                    pNode = L_Rotation(pNode); // 左旋操作
                }
            }
        } else { // ==,更新值
            pNode->value = value;
        }

        // 更新二叉树的高度
        pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
        return pNode;
    }

    // 找最小值，不断往左边找，直到left为null。
    TreeNode<K, V> *minimum(TreeNode<K, V> *pNode) {
        if (pNode->left == NULL) {
            return pNode;
        }
        return minimum(pNode->left); // 递归查找
    }

    // 删除节点---- 移除操作：
    TreeNode<K, V> *removeNode(TreeNode<K, V> *pNode, K key) {
        // 0.递归没有写到底的情况
        if (pNode == NULL) {
            return NULL;
        }

        if (pNode->key > key) { // 1.小，待删除的节点在左子树中
            pNode->left = removeNode(pNode->left, key); // 递归删除节点

            // 高度差超过1，删除左边的，肯定是右边的比左边高度大。
            if (getHeight(pNode->right) - getHeight(pNode->left) == 2) {
                // 删除节点后，AVL树失去平衡，进行相应的调节。
                // 添加节点时，大的那段代码。
                if (getHeight(pNode->right->left) > getHeight(pNode->right->right)) {
                    // 当左孩子的右孩子的高度 大于 左孩子的左孩子的高度。要先左旋再右旋。
                    pNode = R_L_Rotation(pNode);
                } else {
                    pNode = L_Rotation(pNode); // 单左旋
                }
            }
        } else if (pNode->key < key) { // 2.大，待删除的节点在右子树中。
            pNode->right = removeNode(pNode->right, key); // 递归删除节点

            // 删除右边的，肯定是左边的比右边高度大。
            if (getHeight(pNode->left) - getHeight(pNode->right) == 2) {
                // 调整 , 不能简简单单的就做一次右旋
                // 添加节点时，小的那段代码。
                if (getHeight(pNode->left->right) > getHeight(pNode->left->left)) {
                    pNode = L_R_Rotation(pNode);
                } else {
                    pNode = R_Rotation(pNode); // 单右旋
                }
            }
        } else {// 3.相等，tree是对应要删除的目标节点(包含根节点)
            count--; // 要删除了，总数-1.
            if (pNode->left == NULL && pNode->right == NULL) { // eg：被拿取当新根节点了，直接删除根节点。
                // 3.1 左右子树都为空，叶子节点。
                delete pNode;
                return NULL;
            } else if (pNode->left == NULL) {
                // 3.2 左子树是空，右子树非空
                TreeNode<K, V> *right = pNode->right;
                delete (pNode);
                return right;
            } else if (pNode->right == NULL) {
                // 3.3 左子树非空，右子树是空。
                TreeNode<K, V> *left = pNode->left;
                delete (pNode);
                return left;
            } else {
                // 3.4 左右两子树都不为空
                if (getHeight(pNode->left) > getHeight(pNode->right)) {
                    /**主要思路：
                     * 1.在左边找到目标替代节点；深拷贝这个节点，将来作为根节点；
                     * 2.递归调用 removeNode(pNode->left, max->key)，保证左子树中是平衡二叉树(左旋等操作)
                     * 3.新拷贝了当节点，总节点数据 +1；
                     * 4.原根节点的右子树 作为新根节点的右子树；
                     * 5.删除原来根节点pNode；
                     * 6.将深拷贝的节点，作为新的根节点。
                     */

                    // 左边的高度大：去左边找一个来代替 （左边的最大值）
                    TreeNode<K, V> *max = maximum(pNode->left); // 找到目标节点【拷贝一个，挪上来当根节点，然后删除它本身节点；将拷贝的新节点作为pNode】
                    TreeNode<K, V> *successor = new TreeNode<K, V>(max); // 深拷贝对象
                    // 保证移除的子节点的高度都有更新，递归，顺带去更新left子树的高度。
                    successor->left = removeNode(pNode->left, max->key); // 【递归】监测不平衡，可能涉及左旋操作。对左子树旋转。
                    count++; // 新拷贝了当节点，数据+1
                    successor->right = pNode->right;
                    // 更新当前后继的高度
                    delete (pNode);
                    pNode = successor;
                } else {
                    // 右边的高度大 或高度相等 ：去右边找一个来代替 （右边的最小值）
                    TreeNode<K, V> *min = minimum(pNode->right);
                    TreeNode<K, V> *successor = new TreeNode<K, V>(min);
                    // 保证移除的子节点的高度都有更新
                    successor->right = removeNode(pNode->right, min->key);// 【递归】，对右子树，进行旋转操作。
                    count++;
                    successor->left = pNode->left;
                    // 更新当前后继的高度
                    delete (pNode);
                    pNode = successor;
                }
            }
        }

        // 4.移除节点，更新pNode的高度
        pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
        return pNode;
    }

    TreeNode<K, V> *deleteMax(TreeNode<K, V> *pNode) {
        if (pNode->right == NULL) {
            TreeNode<K, V> *left = pNode->left;
            delete (pNode);
            count--;
            return left;
        }
        pNode->right = deleteMax(pNode->right);
        return pNode;
    }
    // 查找当前树的最大值
    TreeNode<K, V> *maximum(TreeNode<K, V> *pNode) {
        // 不断的往右边找，直到找到右子树为空节点
        if (pNode->right == NULL) {
            return pNode;
        }
        return maximum(pNode->right); // 递归查找
    }

    void inOrderTraverse(TreeNode<K, V> *pNode, void (*pFunction)(K, V)) {
        if (pNode == NULL) {
            return;
        }
        inOrderTraverse(pNode->left, pFunction);
        pFunction(pNode->key, pNode->value);
        inOrderTraverse(pNode->right, pFunction);
    }
};
#endif //NDK_DAY44_BST_H

/** 数据为层序打印输出。
 * 原数据【3,1,2】 只进行右旋，变成【1,3,2】还是不平衡，所以不能简单的只进行右旋操作。
 *       // 当左孩子的右孩子的高度 大于 左孩子的左孩子的高度。先进行左旋，再右旋。
 *      要先对左孩子1进行左旋，变成[3,2,1]；再对3进行右旋, 变成[2,1,3]。
 * 原数据【1,3,2】 只进行左旋，变成【3,1,2】还是不平衡，
 *      要先右旋操作 变成[1,2,3]；再左旋操作[2,1,3]。
 *
 * 移除比较复杂
 * 1.当左右不为空，删除最大或最小值，将要作为后继根节点。
 *      要确保在删除最大或最小值时，要更新节点的高度（removeNode）。还要更新当前节点的高度。
 *
 */

